package com.cctc.juc.source.Bitc.Icontainer.hash.rbtree;
/**
 * 【红黑树】底层实现原理。
 * 要求：熟练掌握（手撕、陈述）红黑树底层实现原理、优点、应用场景等。
 * 1. 产生背景（缘由）：
 * 二叉查找树（BST）的缺点：极端情况下会退化成一个链表。
 * 为了避免这种情况发生，引入了自（旋转）平衡的二叉查找树（AVL），通过 “旋转” 操作（左旋、右旋、左右旋、右左旋）来控制 BST 的层数和节点位置，以此达到高度平衡（任何节点的左右子树高度差不大于 1）。
 * 提示：我们只需要聚焦于失衡子树，然后逆向旋转，来维护 AVL 树的平衡特性。
 * - 左左失衡子树，右旋；
 * - 右右失衡子树，左旋；
 * - 左右失衡子树，左旋 + 右旋；
 * - 右左失衡子树，右旋 + 左旋。
 * AVL 树的缺点：对于频繁进行写（插入 | 删除）操作的场景，AVL 树需要花大量的时间用在 “旋转” 平衡调整上，以此来满足其自身及其严格的平衡约束，反而影响了写（插入 | 删除）操作的性能。
 * 为了提升写（插入 | 删除）操作的效率，引入了红黑树（RBTree），通过牺牲部分平衡特性，以减少写（插入 | 删除）操作时的 “旋转” 平衡调整次数。
 * 2. 概述：红黑树是一种比较常用的自平衡二叉查找树，它继承了 AVL 自平衡的优点，但却放宽了 AVL 树严格的平衡约束，即使用非严格的平衡约束来减少写（插入 | 删除）操作时的 “旋转” 平衡调整次数，以此来提升 AVL 写（插入 | 删除）操作的效率。在红黑树中，AVL 节点被表标记为红色和黑色两种颜色，且具有以下 5 个约束条件：
 * - 节点非黑即红；
 * - 根黑，根节点必须是黑色的；
 * - 叶子（NIL）黑，叶子节点也必须是黑色的；
 * - 红中有黑，红色节点的左右孩子节点，也必须是黑色的；
 * - 黑色完美平衡，从任一节点到其叶子节点的每条路径上，都包含有相同数量的黑色节点。
 * 即牺牲（红色）部分节点的平衡性，仅保证黑色（部分）节点的完美平衡特性，以此来减少 AVL 树写（插入 | 删除）操作时的 “旋转” 平衡调整次数，从而提升写（插入 | 删除）操作的性能。
 * 3. 红黑树自平衡操作：变色、左旋、右旋。
 * 4. 红黑树写（插入 | 更新）操作核心流程：
 * 约束：默认新插入的节点都是红色的，以避免打破黑色（部分）节点的完美平衡约束。
 * 1）[首插 - 变色] 起始，红黑树为一颗空树，直接把新插入的红色节点作为根节点，然后将其更新为黑色；
 * 2）如果写（插入 | 更新）节点的关键字 Key 已存在，则为更新操作，只需将目标节点的元素值 Value 更新为新元素值即可；
 * 3）否则，为插入操作，插入新节点：
 * 3.1）[父黑 - 直插] 如果新插入（红色）节点的父节点为黑色，没有破坏平衡约束，直接插入即可；
 * 3.2）如果新插入（红色）节点的父节点为红色，此时会出现两种失衡状态：
 * a. [叔父全红 - 全变色] 父亲和叔叔节点都为红色，为 [颜色失衡]，进行变色平衡处理：
 * - 将父亲和叔叔节点都更新为黑色；
 * - 将祖父节点更新为红色；
 * - 将祖父节点标记为当前（写操作）节点，执行写操作；
 * - 重复执行以上过程，直到平衡。
 * b. 父亲节点为红色，叔叔节点为黑色，且父节点为祖父节点的左 | 右孩子节点，为 [颜色 + 高度失衡]，此时分为两种情况：
 * b.1）[叔黑父红左插入 - 变色 + 旋转] 新插入节点为其父节点的左 | 右孩子节点，为颜色 + 左左 | 右右失衡子树，进行变色 + 旋转平衡处理：
 * - 将父节点更新为黑色；
 * - 将祖父节点更新为红色；
 * - 右 | 左旋父节点；
 * b.2）[叔黑父红右插入 - 变色 + 旋转] 新插入节点为其父节点的右 | 左孩子节点，为颜色 + 左右 | 右左失衡子树，进行变色 + 旋转平衡处理：
 * - 左 | 右旋父节点；
 * - 将父节点标记为当前节点，然后按照 b.1）情况处理。
 * 在红黑树中，任何的 [颜色、颜色 + 高度] 失衡状态都会在三次旋转之内解决，与 AVL 相比，写（插入 | 删除）操作效率更高。
 * 5. 红黑树典型应用场景：
 * - JDK [8] 中的 HashMap，当同一哈希槽中的链表长度超过 8 且 table 数组容量达到 64 时，将会触发树化操作，将单向链表转化为红黑树 + 双向链表，以提升读写效率；
 * - JDK 中的 TreeMap（键值对）、TreeSet（集合）都是基于红黑树实现 Node 节点的有序存储的；
 * - Linux 中的多路 I/O 复用技术中的 Epoll，底层是基于红黑树 + 双向链表进行实现的；
 * - Linux 中的 CFS 进程调度算法中的 vruntime 也是使用红黑树进行有序存储的。
 */